﻿// 1001train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>

using namespace std;

/*
输入
12 7 2 1 1 -1 13
001000010000
001000010000
001000010000
001000010000
001000010000
001000010000
001000010000
输出
3
 */
class Solution01
{
public:
    Solution01(vector<int>&base,vector<vector<int>>&grid)
    {
//12 7 2 1 1 -1 13
/*
w，h为矩阵的宽和高
x，y为起始位置
sx，sy为初始速度
t为经过的时间
*/
        int col_size=base[0], row_size=base[1];
        int r = base[3], c = base[2];
        int sr = base[5], sc = base[4];
        int count = base[6];

        int result = grid[r][c];
        while (count>0)
        {
            if (r+sr==row_size || r+sr==-1)
            {
                sr *= -1;
            }

            if (c+sc==col_size || c+sc==-1)
            {
                sc *= -1;
            }

            r = r + sr;
            c = c + sc;
            result += grid[r][c];
            count--;
	        //while---
        }

        cout << result;
	    //Solution01
    }
};


/*
 输入描述
输入一个string型基因序列，和int型子串的长度

输出描述
找出GC比例最高的子串,如果有多个则输出第一个的子串

输入
AACTGTGCACGACCTGA
5
输出
GCACG

CGACC的GC-Ratio也是最高，从左往右找到的GC-Ratio最高的第2个子串，所以只能输出GCACG
 */
class Solution02
{
public:
    Solution02(string&origin_str, int win_len)
    {
        //CG
        unordered_set<char>char_set={'C', 'G'};
        int curr_count = 0;
        for (int i=0; i<win_len; i++)
        {
	        if (char_set.count(origin_str[i])>0)
	        {
                curr_count++;
	        }
        }

        int result = curr_count;
        int pos = 0;

        int old_left = 0;
        int str_size = origin_str.size();
        for (int left=1,right=win_len; right< str_size; left++,right++)
        {
            if (char_set.count(origin_str[old_left])>0)
            {
                curr_count--;
            }
            if (char_set.count(origin_str[right])>0)
            {
                curr_count++;
            }
            if (curr_count>result)
            {
                pos = left;
                result = curr_count;
            }
            old_left = left;

        }

        cout << origin_str.substr(pos, win_len);
	    //Solution02
    }
};


/*
 给定一个含有N个正整数的数组，求出有多少个连续区间（包括单个正整数）
 它们的和大于等于x

输入描述
第一行两个整数N x (0 < N <= 100000 ,0 <= x <= 10000000)
第二行有N个正整数（每个正整数小于等于100）。

输出描述
输出一个整数，表示所求的个数

输入
3 7
3 4 7
输出
4
 */
class Solution03
{
public:
    Solution03(vector<long long>&num_vec, int X)
    {
        int v_size = num_vec.size();
        vector<long long>pre_sum(v_size+1);

        for (int i=1; i<=v_size; i++)
        {
            pre_sum[i] = pre_sum[i - 1] + num_vec[i-1];
        }

        
        //3 4 7
        //0 3 7 14
        int result = 0;
        int pre_sum_size = v_size + 1;
        for (int i=0; i<v_size; i++)
        {
            long long target = pre_sum[i] + X;
            //前缀和数组是连续递增的
            //找到第一个
            int left = 0, right = v_size + 1;
            int pos = -1;

            while (left<right)
            {
                int mid = left + (right - left) / 2;

                if (pre_sum[mid]>=target)
                {
                    pos = mid;
                    right = mid;
	                //缩小区间
                }
                else
                {
                    left = mid + 1;
                }
                //while---
            }

            if (pos!=-1)
            {
                result += pre_sum_size - pos;
            }

	        //for---
        }

        cout << result;
	    //Solution03
    }
};


/*
输入两个字符串S和L，都只包含小写字母，len(S) <= 100，len(L) <= 500000
判断S是否是L的有效子字符串。
- 判定规则：S中的每个字符在L中都能找到（可以不连续），
且S在L中字符的前后顺序与S中顺序要保持一致。
例如：
S = "ace"是L = "abcde"的一个子序列，
且有效字符是a、c、e，而"aec"不是有效子序列，且有效字符只有a、e（因为相对位置不同）。

输入
输入两个字符串S和L，都只包含小写字母，len(S) <= 100，len(L) <= 500000，先输入S再输入L
每个字符串占一行。

输出描述
S串最后一个有效字符在L中的位置，首位从0开始计算。无有效字符返回 -1

输入
ace
abcde
输出
4
 */
class Solution04
{
public:
    Solution04(string&sub_str,string&origin_str)
    {
        int sub_i = 0;
        int sub_size = sub_str.size();

        int final_i = -1;
        int origin_size = origin_str.size();
        for (int i=0; i<origin_size; i++)
        {
	        if (origin_str[i]==sub_str[sub_i])
	        {
                final_i = i;
                sub_i++;
	        }
        }

        
        cout << final_i;
        

	    //
    }
};

int main()
{
	{
        string sub_str, origin_str;
        cin >> sub_str >> origin_str;

        Solution04 solu(sub_str, origin_str);

        return 0;
	}
	{
/*
3 7
3 4 7
*/
        int v_size, X;
        cin >> v_size >> X;

        vector<long long>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        Solution03 solu(num_vec, X);

        return 0;
	}
	{
        string origin_str;
        cin >> origin_str;

        int win_len;
        cin >> win_len;

        Solution02 solu(origin_str, win_len);
        return 0;
	}
    vector<int>base(7);
    cin >> base[0] >> base[1] >> base[2] >> base[3] >> base[4] >> base[5] >> base[6];

    int col_size = base[0], row_size = base[1];
    vector<vector<int>>grid(row_size, vector<int>(col_size));
    for (int r=0; r<row_size; r++)
    {
        string row_str;
        cin >> row_str;
        for (int c=0; c<col_size; c++)
        {
            grid[r][c] = row_str[c] - '0';
        }
    }
    Solution01 solu(base, grid);
    return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
